public class BinarySearchTree {
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root = null;//定义一个二叉搜索树的根结点
    public TreeNode find(int val){
        TreeNode cur = root;//定义一个cur结点遍历这颗二叉树搜索树,root不动，记录整颗二叉树，别的方法在使用的时候，也可以从root结点开始，防止root在这个方法中移动之后，找不到开始root的位置。
        while(root != null){//假设这颗树还有孩子节点，继续遍历
            if(cur.val > val){//要查找的值，比cur遍历到的结点的值小，则向cur的左子树遍历
                cur = cur.left;
            }else if(cur.val < val){//要查找的值，比cur遍历到的结点的值大，则向cur的右子树遍历
                cur = cur.right;
            }else{
                return cur;//找到了，返回cur走到的结点
            }
        }
        return null;//遍历完都没有找到要查找的值，返回null.
    }
    //插入一个数据
   public void insert(int val){
        if(root == null){//当搜索二叉树为空，则创建一个结点传入val，将其作为根节点
            root = new TreeNode(val);
            return;
        }
        //搜索二叉树不为空
        TreeNode cur = root;//创建一个cur遍历二叉树
        TreeNode parent = root;//创建一个parent变量来记录cur遍历过的结点，防止cur遍历到叶子节点后，继续向下遍历时，丢失对叶子节点的记录
        while(cur != null){//如果cur没有将搜索二叉树遍历完，进入
            if(cur.val > val){//如果cur遍历到的结点的值，比要插入的值大
                parent = cur;//parent先记录cur当前位置
                cur = cur.left;//cur去遍历当前结点的左子树
            }else if(cur.val < val){//当cur遍历到的结点的值，比要插入的值小
                parent = cur;//parent记录当前cur的位置
                cur = cur.right;//cur遍历当前结点的右子树
            }else{//当要插入的值与cur的值相等
                return;//直接返回，因为这是一个搜索二叉树，没有必要有两个相同值的结点，搜索二叉树只是让树中有这个值就行。
            }
        }
        //当cur遍历到的结点为空时，
        TreeNode newNode = new TreeNode(val);//创建一个结点，让其值域为val
        if(parent.val > val){//如果val的值比parent记录的结点的值小
            parent.left = newNode;//将这个结点，放在parent记录的结点的左子树
        }else{//如果val比parent的val大
            parent.right = newNode;//将这个节点，放在parent记录的结点的右子树
        }
   }
    public void remove(int val){
        TreeNode cur = root;//定义cur，遍历要删除的数字
        TreeNode parent = null;//定义parent，记录cur当前所在位置
        while(cur != null){//没有将树遍历完，并且没有找到要删除的值，进入循环
            if(cur.val == val){//找到要删除结点
                removeNode(parent,cur);//将parent,cur结点传给删除操作的方法
            }else if(cur.val < val){//cur遍历到的结点的值，小于要删除的值
                parent = cur;//parent先将cur当前位置记录下来
                cur = cur.right;//cur向搜索二叉树的右子树遍历
            }else{//当cur的值大于要删除的值
                parent = cur;
                cur = cur.left;//cur向搜索二叉树的左子树遍历
            }
        }
}
    /*
    * 删除操作
    * */
    private void removeNode(TreeNode parent, TreeNode cur) {
        //cur的左子树为空
        if(cur.left == null){
            //cur指向root结点
            if(cur == root){
                root = root.right;//将root结点删除之后，新的root为root的右子树
            //cur是parent的左子树，但cur没有左子树
            } else if (parent.left == cur) {
                parent.left = cur.right;//将cur删掉之后，parent的左子树指向cur的右子树
            //cur是parent的右子树，但是cur没有左子树
            }else{
                parent.right = cur.right;//将cur删除之后，cur的右子树传递给parent的右子树
            }
            //cur的右子树为空
        }else if(cur.right == null){
            //cur指向根节点
            if(cur == root){
                root = cur.left;//因为cur没有右子树，所以将cur删除之后，cur的左子树作为新的根结点
            //cur是parent的左子树，但是cur没有右子树
            }else if(parent.left == cur){
                parent.left = cur.left;//将cur删除之后，cur的左子树传给parent的左子树
            //cur是parent的右子树，但是cur没有右子树
            }else{
                parent.right = cur.left;//将cur删除之后，cur的左子树传递给parent的右子树
            }
            //cur的左右子树都不为空
        }else{
            TreeNode target = cur.right;//定义target指向cur结点的右子树
            TreeNode targetParent = cur;//定义targetParent指向cur结点
            //当target的左子树不为空，则进入循环，直到找到的target没有左孩子，但有可能存在右孩子
            while(target.left != null){
                targetParent = target;
                target = target.left;
            }
            //当找到没有左孩子的target结点，或者在指定target等于cur的右子树的时候，target就没有左孩子结点，target为targetParent的右孩子节点
            cur.val = target.val;//将target的值赋给cur结点，这样就将要删除的值，转换为删除target结点
            //如果是通过循环找到的target结点
            if(target == targetParent.left){
                targetParent.left = target.right;//将target结点的右孩子结点传给targetParent结点的左子树
            //如果target是targetParent的右孩子结点
            }else{
                targetParent.right = target.right;//将target结点的右孩子结点传给targetParent结点的右孩子结点
            }
        }
    }
}
